#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Node {
	int power; //结点的权值
	Node* lchild,
		* rchild;// 左右子树
};

class HuffmanTree {
public:
	const int& PWL; //树的权值（只读）
	const vector<int>& powers; //权值数组（只读）
	const vector<string>& codes; //编码数组（只读）

	HuffmanTree();
	~HuffmanTree();
	void Create(vector a); //创建哈夫曼树
private:
	vector<Node*> _forest;//哈夫曼森林
	vector<int> _powers; //权值数组
	vector<string> _codes;//编码数组
	int _pwl; //树的权值

	void Release(Node*); //递归销毁树
	void Coding(Node*, const string&); //递归编码
	void AddNode(Node* s);//将结点 s 加入到森林(链表)，并确保链表各结点的权值是从小到大排列
};

HuffmanTree::HuffmanTree() :PWL(_pwl), powers(_powers), codes(_codes) {};

HuffmanTree::~HuffmanTree() {};

//创建哈夫曼树
void HuffmanTree::Create() {
	int power;
	while (cin >> power, power > 0) {
		_powers.push_back(power);
		_codes.push_back("");
		Node* s = new Node();
		s->power = power;
		s->lchild = s->rchild = NULL;
		AddNode(s);
	}

	//创建树的过程
	while (_forest.size() > 1) {
		Node* p1, * p2, * p3;
		p1 = _forest.front(); //最小权值
		_forest.erase(_forest.begin());
		p2 = _forest.front(); //次小权值
		_forest.erase(_forest.begin());//组装新结点, p1 和 p2 分别为其左右子树
		p3 = new Node();
		p3->power = p1->power + p2->power;
		p3->lchild = p1;
		p3->rchild = p2;
		//将结点加入到森林(加入链接)
		AddNode(p3);
	}

	//从根结点开始编码
	_pwl = 0;
	if (_forest.size() > 0) {
		Coding(_forest[0], "");
		Release(_forest[0]);
	}
}

//递归销毁树
void HuffmanTree::Release(Node* node)
{
	if (NULL == node) return;
	Release(node->lchild);
	Release(node->rchild);
	delete node;
}

//递归打印编码
void HuffmanTree::Coding(Node* node, const string& code)
{
	if (NULL == node->lchild && NULL == node->rchild) { //叶结点
	//累加权值
		_pwl += node->power * code.length();
		//将编码写入结果数组
		int i = 0;
		while (_powers[i] != node->power || _codes[i].length() > 0) i++;
		_codes[i] = code;
	}
	else {
		if (node->lchild) Coding(node->lchild, code + "0");
		if (node->rchild) Coding(node->rchild, code + "1");
	}
}

//将结点 s 加入到森林(链表)，并确保森林各结点的权值是从小到大排列
void HuffmanTree::AddNode(Node* s)
{
	vector<Node*>::iterator i = _forest.begin();
	while (i != _forest.end() && (*i)->power <= s->power) i++;
	//将新结点 s 放到 p 的后面
	_forest.insert(i, s);
}

int main()
{
	int n,
		i;

	cin>>n;
	vector<vector<int>> a(n);

	for (i = 0; i < n; i++)
	{
		int j=-1;
		do
		{
			j++;
			cin>>a[i][j];
		} while (a[i][j]);
	}

	HuffmanTree ht;
	for (i = 0; i < n; i++)
	{
		ht.Create(a[i]);
		cout << ht.PWL << endl;
	}

	system("pause");
	return 0;
}
